import java.util.*;

public class Solution {

    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < jewels.length(); i++) {
            char ch1 = jewels.charAt(i);
            set.add(ch1);
        }
        int count = 0;
        for (int i = 0; i < stones.length(); i++) {
            char ch2 = stones.charAt(i);
            if (set.contains(ch2)) {
                count++;
            }
        }
        return count;
    }

    public static List<String> topKFrequent(String[] words, int k) {
        //记录每个字符在words中的次数
        Map<String,Integer> hashMap = new HashMap<>();
        for (String s: words) {
            if (hashMap.get(s) == null) {
                hashMap.put(s,1);
            }else {
                hashMap.put(s,hashMap.get(s)+1);
            }
        }
        //建立一个小根堆
        PriorityQueue<Map.Entry<String,Integer>> minheap = new PriorityQueue<>(k,new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if (o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });
        //将hashMap的值放入小根堆中，小根堆的大小为k
        for (Map.Entry<String,Integer> word : hashMap.entrySet()) {
            if (minheap.size() < k) {
                minheap.offer(word);
            }else {
                Map.Entry<String,Integer> top = minheap.peek();
                if (top.getValue().compareTo(word.getValue()) < 0) {
                    minheap.poll();
                    minheap.add(word);
                }else {
                    if (top.getValue().compareTo(word.getValue()) == 0) {
                        if (top.getKey().compareTo(word.getKey()) > 0) {
                            minheap.poll();
                            minheap.add(word);
                        }
                    }
                }
            }
        }
        //System.out.println(minheap);
        List<String> list = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            String key = minheap.poll().getKey();
            list.add(key);
        }
        Collections.reverse(list);
        return list;
    }

    public static void main(String[] args) {
        String[] words = {"a","b","a","c","d","a","c","e","e","a","e"};
        List<String> ret = topKFrequent(words,3);
        System.out.println(ret);
    }

}
